#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    // 查看区间是否重叠，首先判断区间的右端点和new左端点的位置
    // 如果区间的右端点和new左端点没有重叠则不重合(>=)
    // 如果区间的右端点和new左端点重叠,此时如果区间的左端点和new右端点重叠则重合
    int i = 0, n = intervals.size();
    vector<vector<int>> res;
    // 注意要一次遍历完所有未重叠的，一次遍历完所有重叠的
    while(i < n && intervals[i][1] < newInterval[0]) {
        res.push_back(intervals[i]);
        ++i;
    }
    while(i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        ++i;
    }
    res.push_back(newInterval);
    // 剩下的都是不重叠的
    while(i < n) {
        res.push_back(intervals[i]);
    }
    return res;
}